package top.lcm668.study.oj.base.sortmethods;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author: Coder-Lcm
 * @date: 2021/10/5 16:56
 * 计数排序：为方便验证，T手动改为Integer
 */
public class CountingSort<T extends Comparable<T>> extends BaseSort<T> {

    @Override
    protected void sort(T[] arr, boolean isAsc) {
        if (arr == null || arr.length <= 1) return;
        Integer[] nums = (Integer[]) arr;
        int bias, min = nums[0], max = nums[0];

        // 找出最大值，最小值
        for (int i = 1; i < nums.length; i++) {
           max = Math.max(max, nums[i]);
           min = Math.min(min, nums[i]);
        }

        bias = 0 - min;
        int[] bucket = new int[max - min + 1];
        Arrays.fill(bucket, 0);

        for (int i = 0; i < nums.length; i++) {
            bucket[nums[i] + bias]++;
        }
        int index = 0, i = 0;
        while (index < nums.length) {
            if (bucket[i] != 0) {
                nums[index] = i - bias;
                bucket[i] --;
                index++;
            } else {
                i++;
            }
        }
        arr = (T[]) nums;
    }
}
